/* Este modulo extiende la funcionalidad de */
#include "include/radix_tree_tag_count.h"

#ifdef __KERNEL__
#define RADIX_TREE_MAP_SHIFT    6
#else
#define RADIX_TREE_MAP_SHIFT    3       /* For more stressful testing */
#endif

#define RADIX_TREE_MAP_SIZE     (1UL << RADIX_TREE_MAP_SHIFT)
#define RADIX_TREE_MAP_MASK     (RADIX_TREE_MAP_SIZE-1)

#define RADIX_TREE_TAG_LONGS    \
         ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)

struct radix_tree_node {
        unsigned int    count;
        void            *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
                int offset)
{
         return test_bit(offset, node->tags[tag]);
}


int
radix_tree_tag_count(struct radix_tree_node *node, unsigned int height, int tag)
{
	int i;
	int aux = 0;
	if ( height == 1 )
	{
		/* Cuento la cantidad de tags */
		for ( i = 0; i < RADIX_TREE_MAP_SIZE ; i++ )
			if ( node->slots[i] != NULL )
				if (tag_get(node->slots[i], tag, i))
					aux++;
	}
	else
	{
		for ( i = 0; i < RADIX_TREE_MAP_SIZE ; i++ )
		{
			if ( node->slots[i] != NULL )
				aux += radix_tree_tag_count( node->slots[i], height - 1,tag); 
		}
	}
	return aux;
}
